{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于用户的协同过滤\n",
    "\n",
    "## 定义\n",
    "\n",
    "在一个推荐系统中，如果需要对A进行个性化推荐，可以首先寻找与A具有相似兴趣的用户，然后把这些鱼A相似的用户喜欢的、而A没有听说过的物品推荐给A。这种方法称为基于用户的协同过滤算法。\n",
    "\n",
    "这个问题可以分为两步\n",
    "\n",
    "- 找到和目标用户兴趣相似的用户集合\n",
    "\n",
    "-  找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户\n",
    "\n",
    "## 计算兴趣相似度\n",
    "\n",
    "现在给定两个用户 u 和 v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v)为用户v曾经有过正反馈的物品集合，那么我们可以用很多方法表示两者的相似度，下面简单介绍两种。\n",
    "\n",
    "### Jaccard公式\n",
    "\n",
    "$$w_{uv} = \\frac{|N(u) \\cap N(v)|}{|N(u) \\cup N(v)|}$$\n",
    "\n",
    "### 余弦相似度\n",
    "\n",
    "$$w_{uv} = \\frac{|N(u)| \\cap |N(v)|}{\\sqrt{|N(u)| |N(v)|}}$$\n",
    "\n",
    "### 例子\n",
    "\n",
    "下面我们假设有用户A、B、C、D和物品a、b、c、d、e。我们列出用户和正反馈商品之间的关系。\n",
    "\n",
    "| User | Item |\n",
    "| - | - |\n",
    "| A | a b d |\n",
    "| B | a c |\n",
    "| C | b e |\n",
    "| D | c d e |\n",
    "\n",
    "我们使用余弦相似度来举例，用户A和用户B之间的相似度\n",
    "\n",
    "$$w_{AB} = \\frac{|\\{a,b,d\\} \\cap \\{a,c\\}|}{\\sqrt{|\\{a,b,d\\}||\\{a,c\\}|}} = \\frac{1}{\\sqrt 6}$$\n",
    "\n",
    "同理可得\n",
    "\n",
    "$$w_{AC} = \\frac{1}{\\sqrt 6}$$\n",
    "\n",
    "$$w_{AD} = \\frac{1}{3}$$\n",
    "\n",
    "## 相似度计算时的问题\n",
    "\n",
    "### 问题\n",
    "\n",
    "对两两用户都利用余弦相似度计算相似度。这种方法的时间复杂度是 $O(|U| * |U|)$ ，在用户数很大时非常耗时。而实际上，很多用户之间并没有这样都相同物品产生过正反馈，也就是说，很多时候 $|N(u) \\cap N(v)| = 0$ ，将很多时间浪费在计算无关用户的相似度上。\n",
    "\n",
    "### 解决办法\n",
    "\n",
    "我们可以先计算出 $|N(u) \\cap N(v)| \\not= 0$ 的用户对(u, v)，然后再计算相似度。\n",
    "\n",
    "- 首先建立物品到用户的倒排表\n",
    "\n",
    "- 建立稀疏矩阵C，令$C[u][v] = |N(u) \\cap N(v)|$\n",
    "\n",
    "- 扫描倒排表中每个物品对应的用户列表，将用户列表中的两两用户对应的$C[u][v] += 1$\n",
    "\n",
    "- 根据矩阵C计算用户之间的相似度\n",
    "\n",
    "#### 倒排表\n",
    "\n",
    "| Item | User |\n",
    "| - | - |\n",
    "| a | A B |\n",
    "| b | A C |\n",
    "| c | B D |\n",
    "| d | A D |\n",
    "| e | C D |\n",
    "\n",
    "#### 稀疏矩阵C\n",
    "\n",
    "|User|A|B|C|D|\n",
    "|-|-|-|-|-|\n",
    "|A|0|1|1|1|\n",
    "|B|1|0|0|1|\n",
    "|C|1|0|0|1|\n",
    "|D|1|1|1|0|\n",
    "\n",
    "## 物品推荐\n",
    "\n",
    "得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。\n",
    "\n",
    "### 度量用户对物品感兴趣的程度\n",
    "\n",
    "接下来，我们来度量用户 u 对物品 i 的感兴趣程度，我们用 S(u, K) 表示和用户u兴趣最接近的 K 个用户的集合， 用 N(i) 表示对物品i有过行为的用户集合，用 $w_{uv}$ 表示用户u和用户v的兴趣相似度， 用$r_{vi}$ 表示用户v对物品i的兴趣，因为我们这里使用的是单一行为的隐反馈数据，所以所有的$r_{vi} = 1$。\n",
    "\n",
    "$$p(u, i) = \\sum_{v \\in S(u, K) \\cap N(i)} w_{uv} r_{vi}$$\n",
    "\n",
    "假设我们取 K = 3，用户  A对物品 c、e 没有过行为，因此可以把这两个物品推荐给用户 A。\n",
    "\n",
    "$$p(A, c) = w_{AB}r_{Bc} + w_{AD}r_{Dc} = \\frac{1}{\\sqrt 6} * 1 + \\frac{1}{3} * 1 \\approx 0.7416$$\n",
    "\n",
    "$$p(A, e) = w_{AC}r_{Ce} + w_{AD}r_{De} = \\frac{1}{\\sqrt 6} * 1 + \\frac{1}{3} * 1 \\approx 0.7416$$\n",
    "\n",
    "## 算法中超参数K\n",
    "\n",
    "超参数K代表为每个用户选出K个和他兴趣最相似的用户，然后推荐那K个用户感兴趣的物品。\n",
    "\n",
    "K的选取不同可能会产生不同的影响：\n",
    "\n",
    "- 准确率和召回率：选择合适的K对于获得高的推荐系统精度比较重要，但是推荐结果对K也不是特别敏感，只要再一定合适的区域内，都可以获得不错的精度。\n",
    "\n",
    "- 流行度：K越大流行度越高，反之亦然。\n",
    "\n",
    "- 覆盖率：K越大覆盖率越低，反之亦然。\n",
    "\n",
    "K对流行度和覆盖率的影响主要原因是应为，K越大，越倾向于选择热门的物品。\n",
    "\n",
    "## 相似度公式优化\n",
    "\n",
    "特别热门的物品会干扰相似度的计算，对冷门物品的采样更能体现用户的相似度。正如同样购买《固体物理》的用户相似度比同样购买字典的用户高。\n",
    "\n",
    "John S. Breese在论文中提出了如下公式，根据用户行为计算用户的兴趣相似度：\n",
    "\n",
    "$$w_{uv} = \\frac{\\sum_{i \\in N(u) \\cap N(v)} \\frac{1}{log(1+|N(i)|)}}{\\sqrt{|N(u)| |N(v)|}}$$\n",
    "\n",
    "在公式中可以很好的看到 $\\frac{1}{log(1+|N(i)|)}$ 很好的惩罚了用户 u 和 用户 v 共同兴趣列表中热门物品的影响。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**John S. Breese在论文参见John S. Breese、 David Heckerman和 Carl Kadie的论文“ Empirical Analysis of Predictive Algorithms for\n",
    "Collaborative Filtering”（Morgan Kaufmann Publishers，1998）。**\n",
    "\n",
    "**注：本文档中数据和公式来自 项亮先生的《推荐系统实践》 一书，如有侵权，请联系[我](https://github.com/TobiahShaw/tensorflow_hello/issues)**"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
